package Project.LinkList;


class Node {               // 创建单链表的类，和C语言中的构造方法类似
    public int data;
    public Node next;      // 对应的单链表的对象的引用，就是地址

    public Node(int data) {
        // 使用构造方法对其单链表的初始化，创建节点
        this.data = data;
        this.next = null;
    }

}


public class MyLinkList {

    public Node head;


//    头插法
    /*
    两种情况 1.空链表，不是空链表
    **/
    public void addFirst(int data) {
        Node node = new Node(data);  // 创建节点

        if(this.head == null) {
            // 1. 为空链表,直接置换
            this.head = node;
            return; // 程序执行完停止
        }

        // 2.不是空链表
        node.next = this.head;
        this.head = node;

    }



//    打印单链表
    public void disPlay() {
        Node cur = this.head;   // 首节点的拷贝，代替移动

        while(cur != null) {    // 循环遍历到尾节点 null
            System.out.print(cur.data+" ");
            cur = cur.next;     // 移动节点
        }
        System.out.println();
    }



//    尾插法
    /*
    1.链表为空
    2，链表不为空，null ，找尾节点
    * */
    public void addList(int data) {
        Node node = new Node(data);   // 创建节点
        Node cur =  this.head;        // 对首节点拷贝

        // 链表为空
        if(this.head == null) {
            this.head = node;
            return;  // 程序执行完停止
        }

        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }



//    尾删法
    /*
    三种情况
    1.空链表，不用删除
    2.只有首节点，首节点置为null
    3.多个节点的存在
    * */
    public void deleteList() {
        Node cur = this.head;
        Node tmp = this.head.next;

        //     1.空链表，不用删除
        if(this.head == null) {
            throw new RuntimeException("空链表不用删了");
        }

        // 2.只有首节点，首节点置为null
        if(this.head.next == null) {
            this.head = null;
            return; // 把首节点删除了
        }

        // 3.多个节点的存在
        while(tmp.next != null) {
            cur = tmp;
            tmp = tmp.next;
        }
        cur.next = null;
    }



//    查找是否包含关键字 key 是否在单链表当中
    public boolean contains(int key) {
        Node node = this.head;   // 首节点的拷贝

        while(node != null) {
            if(key == node.data) {
                return true;     // 存在该数值的节点
            }
            node = node.next;    // 移动节点
        }
        return false; // 不存在该数值的节点
    }



//    该单链表的长度
    public int size() {
        if(null == this.head) {
            throw new RuntimeException("该单链表为空");
        }

        int count = 0;
        Node cur = this.head;  // 首节点的拷贝，代替首节点的，移动
        while(cur != null) {   // 循环遍历，单链表
            count ++;
            cur = cur.next;    // 移动节点
        }
        return count;
    }



//    查找 x 序号的地址
    private Node searchIndex(int x) {
        Node cur = this.head;     // 对首节点的拷贝，代替移动
        if(x < 0 || x > size() ) {
            throw new RuntimeException("该序号不合理");
        }

        while((x-1) != 0) {       // 注意序号是从0 开始的 所以减 1；
            cur = cur.next;       // 移动节点
            x--;

        }
        return cur;               // 返回该节点的地址
    }



// 在某个 序号后面插入数据节点
    /* 三种情况
    1.在开头，可以复用 头插法
    2.在尾部，可以复用 尾插法
    3.在中间，
    * */
    public void addIndex(int index,int data) {

        //1. 在开头
        if(index == 0 ) {
            addFirst(data);
            return;             // 完成插入，程序停止执行
        }

        //2. 在尾部
        if(index == size()) {
            addList(data);
            return;             // 完成插入，程序停止执行
        }
        //3. 在中间
        Node node = new Node(data);  // 创建节点
        Node cur = searchIndex(index);  // 对应序号的节点的地址
        node.next = cur.next;  // 注意：其中的顺序，不要把链表丢了
        cur.next  = node;

    }

//    查找数值 key 的地址
    private Node searchPrev(int key) {
        Node cur = this.head;      // 首节点的拷贝，代替首节点，移动
        if(this.head == null) {
            throw new RuntimeException("链表为空，不用找了");
        }

        while(cur.next != null) {
            if(cur.next.data == key) {
                return cur;        // 找到，返回该数值的前驱节点
            } else {
                cur = cur.next;    // 移动节点
            }

        }
        return null; // 没有找到，返回 null
    }



//    删除第一个数值为 key 的节点
    /*
    三种情况：
    1.空链表，不用删了
    2.位于首节点
    3.在中间位置
    * */
    public void remove(int key) {
        // 1. 空链表
        if(this.head == null) {
            return;      // 空链表，不用删了
        }

        // 该数值的节点，位于首节点
        if(key == this.head.data) {
            this.head = this.head.next;
            return ;
        }
        Node prev = searchPrev(key);  // 该数值的前驱节点
        if(null == prev) {
            System.out.println("该数值的节点，不存在");
            return;
        }
        prev.next = prev.next.next;

    }



//    删除所有数值为 key 的节点
    public void removeKey(int key) {
        Node prev = this.head;
        Node cur = this.head.next;

        while(cur != null) {

            if(key == cur.data) {   // 对应数值节点的删除
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
            // 首节点删除
            if(key == this.head.data) {
                this.head = this.head.next;
            }


        }

    }



//    清空单链表
    public void clear() {
        this.head = null;
    }
    /*
    注意:明白一点：JVM是有自动回收空间的时候，但是只有没有对象
    引用它的时候，JVM虚拟机才会，回收该空间的，在有人引用了它的时候是不会
    被回收的，当我们把首节点置为null的时候，也就不会有对下面的节点，引用了
    JVM虚拟机就会自动回收内存了
    * */

}
